/**
 * @file LGraph.h
 * @author 黄志烨 (matsuri@bupt.edu.cn)
 * @brief 邻接表的定义及其操作集，只适用于节点存储元素为char类型，权为整数的图，是否有向图需要自行修改InsertEdge函数 ↓
 * @version 0.1
 * @date 2022-05-25
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#ifndef LGRAPG_H
#define LGRAPG_H

#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 100
typedef int Vertex;
typedef int WeightType;
typedef char DataType;

/* 边定义 */
typedef struct ENode *PtrToENode;
struct ENode
{
    Vertex V1, V2; /* 有向边<V1, V2> */
    WeightType Weight; /* 边的权重 */
};
typedef PtrToENode Edge;

/* 邻接点定义 */
typedef struct AdjNode *PtrToAdjNode;
struct AdjNode
{
    Vertex AdjVer; /* 邻接点序号,用来在顶点表中查找对应顶点 */
    WeightType Weight; /* 表头节点通向该顶点的边的权重 */
    PtrToAdjNode Next; /* 表头节点的下一个邻接点 */
};

/* 顶点表头结点定义 */
typedef struct VNode
{
    PtrToAdjNode FirstEdge; /* 第一条边，通向第一个邻接点 */
    DataType Data; /* 表头节点存储的数据 */
} AdjList[MaxVertexNum];

/* 邻接表存储的图的定义 */
typedef struct GNode *PtrToGNode;
struct GNode
{
    int Nv; /* 图中顶点数量 */
    int Ne; /* 图中边的数量 */
    AdjList G; /* 用邻接表表示的图 */
};
typedef PtrToGNode LGraph;

LGraph CreateGraph(int VerticesNum);

void InsertEdge(LGraph Graph, Edge E);

LGraph BuildGraph();

/**
 * @brief 初始化一个有VerticesNum个顶点，但是没有边的图（表顶点边设置为NULL）
 * 
 * @param VerticesNum 目标顶点数量
 * @return LGraph 有VerticesNum个顶点，但是没有边的图
 */
LGraph CreateGraph(int VerticesNum) {
    LGraph Graph;

    Graph = (Graph) malloc(sizeof(struct GNode));
    Graph->Ne = 0;
    Graph->Nv = VerticesNum;

    for (Vertex V = 0; V < VerticesNum; V++)
    {
        Graph->G->FirstEdge = NULL;
    }

    return Graph;
    
}

/**
 * @brief 把边插入邻接表表示的图
 * 
 * @param Graph 目标图
 * @param E 待插入边
 */
void InsertEdge(LGraph Graph, Edge E) {
    // temp暂存顶点V1的第一个邻接点
    PtrToAdjNode temp = Graph->G[E->V2]->FirstEdge; 

    /* 新建目标邻接点V2，Next指向原第一个邻接点（可能为NULL） */
    PtrToAdjNode AdjV = (PtrToAdjNode) malloc(sizeof(struct AdjNode));
    AdjV->AdjVer = E->V2;
    AdjV->Weight = E->Weight;
    AdjV->Next = temp;

    // 顶点V1的第一个邻接点变更为目标邻接点V2
    Graph->G[AdjV->AdjVer]->FirstEdge = AdjV; 


    // 如果是无向图，还要反向操作一波 ↓

    // temp暂存顶点V2的第一个邻接点
    temp = Graph->G[E->V2]->FirstEdge; 

    /* 新建目标邻接点V1，Next指向原第一个邻接点（可能为NULL） */
    AdjV = (PtrToAdjNode) malloc(sizeof(struct AdjNode));
    AdjV->AdjVer = E->V1;
    AdjV->Weight = E->Weight;
    AdjV->Next = temp;

    // 顶点V2的第一个邻接点变更为目标邻接点V1
    Graph->G[AdjV->AdjVer]->FirstEdge = AdjV; 
}

/**
 * @brief 依次输入顶点数，边数，每条边的信息完成建图
 * 
 * @return LGraph 一个建立好的图
 */
LGraph BuildGraph() {
    int nv;
    LGraph Graph;

    scanf("%d ", &nv); /* 读入顶点数 */
    Graph = CreateGraph(nv); /* 建立有nv个顶点的邻接表表示的无边图 */

    scanf("%d", &(Graph->Ne)); /* 读入边数 */

    /* 如果有边 */
    if (Graph->Ne != 0) {
        Edge E = (Edge) malloc(sizeof(struct ENode));

        for (int i = 0; i < Graph->Ne; i++)
        {
            scanf("%d %d %d", &(E->V1), &(E->V2), &(E->Weight)); /* 输入边的起点（尾），终点（头），权重信息 */
            InsertEdge(Graph, E); /* 插入边 */
        }
        
    }

    /* 如果顶点需要存储数据 */
    for (Vertex V = 0; V < Graph->Nv; V++)
    {
        scanf("%c", &(Graph->G[V].Data));
    }

    return Graph;
}

#endif


